package datastructure.avl;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author XY
 * @version 1.0
 * @date 2021/12/30 9:27
 * @Description
 */
public class AVLTree<K extends Comparable<K>, V>{

    private class Node{
        public K key;
        public V value;
        public Node left,right;
        public int height;

        public Node(K key, V value){
            this.key = key;
            this.value = value;
            left = null;
            right = null;
            height = 1;
        }

        @Override
        public String toString() {
            return key.toString()+":"+value.toString();
        }
    }

    private Node root;
    private int size;

    public AVLTree(){
        root =null ;
        size = 0;
    }

    private int getHeigth(Node node){
        if(node==null){
            return 0;
        }
        return node.height;
    }

    private int getBalanceFactor(Node node ){
        if(node == null){
            return 0;
        }
        return getHeigth(node.left)-getHeigth(node.right);
    }

    public void add(K key, V value) {

        root = add(root,key,value);

    }

    private Node add(Node node, K key, V value) {
        //如果递归到某个节点为null， 那么插入的地方一定是这个节点。
        if(node==null){
            size++;
            return new Node(key,value);
        }
        if(key.compareTo(node.key)<0){
            node.left = add(node.left,key,value);
        }else if (key.compareTo(node.key)>0){
            node.right = add(node.right,key,value);
        }else{
            //相等的情况下覆盖原值
            node.value = value;
        }
        //更新height
        node.height=1+Math.max(getHeigth(node.left),getHeigth(node.right));
        //计算平衡因子
        int balanceFactor = getBalanceFactor(node);
//        if(Math.abs(balanceFactor)>!){
//            System.out.println("不是平衡二叉树");
//        }
        return node;

    }



    public boolean contains(K key) {
        return getNode(root,key)!=null;
    }

    public V get(K key) {
        Node node = getNode(root, key);
        return node ==null?null:node.value;
    }
    private Node getNode(Node node,K key){
        if(node == null){
            return null;
        }
        if(key.compareTo(node.key)==0){
            return node;
        }else if (key.compareTo(node.key)<0){
            return getNode(node.left,key);
        }else{
            return getNode(node.right,key);
        }
    }

    public void set(K key, V value) {
        Node node = getNode(root, key);
        if(node == null){
            throw  new RuntimeException(key+" is not exist!");
        }
        node.value = value;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    private Node minimum(Node e){
        if(e.left == null){
            return e;
        }
        return minimum(e.left);
    }

    private Node removeMin(Node node){

        //判断是最小的节点了
        if(node.left == null){
            //这里如果右子节点为null也不影响
            Node rightNode = node.right;
//            可省略？？
            node.right=null;
            size --;
            return rightNode;
        }
        node.left = removeMin(node.left);
        return node;
    }

    public V remove(K key) {
        Node node = getNode(root, key);
        if(node != null){
            root = remove(root,key);
            return node.value;
        }
        return null;
    }

    private Node remove(Node node, K key) {
        if(node==null){
            return null;
        }
        if(key.compareTo(node.key)<0){
            node.left = remove(node.left,key);
            return node;
        }else if(key.compareTo(node.key)>0){
            node.right = remove(node.right,key);
            return node;
        }else{
            if(node.left==null){
                //这里如果右子节点为null也不影响
                Node rightNode = node.right;
                //可省略？？
                node.right=null;
                size --;
                return rightNode;
            }
            if(node.right==null){
                //这里如果左子节点为null也不影响
                Node leftNode = node.left;
                node.left=null;
                size --;
                return leftNode;
            }
            //要删除的节点左右孩子都存在，选在该节点右子树中最小的元素成为删除后的新的根节点
            Node minimum = minimum(node.right);
            minimum.right = removeMin(node.right);
            minimum.left = node.left;
            node.left = node.right = null;
            return minimum;

        }

    }


}